package main.leetcode.offer.secondround.from03to50;

/** 03.数组中重复的数字 */
public class ex03 {
    public static void main(String[] args) {
        System.out.println(new ex03().findRepeatNumber(new int[] {2, 3, 1, 1, 2, 5, 3}));
        System.out.println(
                new ex03()
                        .findRepeatNumber(
                                new int[] {0, 1, 2, 3, 4, 11, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15}));
    }
    // 计数
    //    public int findRepeatNumber(int[] nums) {
    //        int[] counter = new int[100000];
    //        for (int i : nums) {
    //            if (counter[i] > 0) return i;
    //            ++counter[i];
    //        }
    //        return 0;
    //    }

    // 原地哈希
    //    public int findRepeatNumber(int[] nums) {
    //        int tmp;
    //        for (int i = 0; i < nums.length; ++i) {
    //            while (nums[i] != i) {
    //                tmp = nums[i];
    //                if (tmp == nums[tmp]) return tmp;
    //                nums[i] = nums[tmp];
    //                nums[tmp] = tmp;
    //            }
    //        }
    //        return -1;
    //    }

    public int findRepeatNumber(int[] nums) {
        int tmp;
        for (int i = 0; i < nums.length; ++i) {
            tmp = Math.abs(nums[i]);
            if (nums[tmp] < 0) return tmp;
            nums[tmp] = nums[tmp] * -1;
        }
        return -1;
    }
}
